{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6baf2598",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-22T21:06:33.084910Z",
     "start_time": "2022-10-22T21:06:33.065246Z"
    }
   },
   "source": [
    "<br><font face=\"Times New Roman\" size=5><div dir=ltr align=center>\n",
    "<font color=blue size=8>\n",
    "    Introduction to Machine Learning <br>\n",
    "<font color=red size=5>\n",
    "    Sharif University of Technology - Computer Engineering Department <br>\n",
    "    Fall 2022<br> <br>\n",
    "<font color=black size=6>\n",
    "    Homework 2: Practical - Decision Tree   \n",
    "<font color=black size=4>\n",
    "    Hamidreza Yaghoubi \n",
    "    \n",
    "<br><br>\n",
    "<font size=4>\n",
    "In this homework, we are going to implement the Classification Decision Tree. Keep in mind to complete all of the following questions and write your own codes in the TODO cells."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd3871b7",
   "metadata": {},
   "source": [
    "<font face=\"Times New Roman\" size=4><div dir=ltr>\n",
    "# Problem 2: Classification Decision Tree (100 points)\n",
    "We will implement a Classification Decision Tree from scratch in the following problem. Then we will use our model to predict malignant and benign breast cancer. For this purpose, we will use the breast_cancer.csv dataset which you can find more details about it <a href=\"https://www.kaggle.com/datasets/merishnasuwal/breast-cancer-prediction-dataset\"><font face=\"Roboto\">here</font></a>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ccdebb27",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-22T21:30:24.876526Z",
     "start_time": "2022-10-22T21:30:24.439793Z"
    }
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import accuracy_score\n",
    "from math import log\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2307c50",
   "metadata": {},
   "source": [
    "<font face=\"Times New Roman\" size=4><div dir=ltr>\n",
    "## Classification Decision Tree Class (60 points)\n",
    "In this section, you only need to fill TODO parts. You can find the logic and formula in both course slides and the web, but fill it out on your own. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "618baebb",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-22T21:30:25.034364Z",
     "start_time": "2022-10-22T21:30:25.021627Z"
    }
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):\n",
    "        self.feature = feature\n",
    "        self.threshold = threshold\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.value = value\n",
    "\n",
    "    def is_leaf(self):\n",
    "        if self.value is not None:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "71b3b483",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-22T21:30:25.439792Z",
     "start_time": "2022-10-22T21:30:25.404649Z"
    }
   },
   "outputs": [],
   "source": [
    "class DecisionTree:\n",
    "    def __init__(self, max_depth=None, min_samples_split=2):\n",
    "        self.max_depth = max_depth\n",
    "        self.min_samples_split = min_samples_split\n",
    "        self.root = None\n",
    "\n",
    "    def is_splitting_finished(self, depth, num_class_labels, num_samples):\n",
    "\n",
    "        #TODO\n",
    "\n",
    "        return None\n",
    "\n",
    "    def split(self, X, y, feature, threshold):\n",
    "        left_indexes = X[feature] <= threshold\n",
    "        right_indexes = -left_indexes\n",
    "        X_left = X[left_indexes]\n",
    "        y_left = y[left_indexes]\n",
    "        X_right = X[right_indexes]\n",
    "        y_right = y[right_indexes]\n",
    "\n",
    "        return X_left, X_right, y_left, y_right\n",
    "\n",
    "    def entropy(self, y):\n",
    "        \n",
    "        #TODO\n",
    "        \n",
    "        return ent\n",
    "\n",
    "\n",
    "    def information_gain(self, X, y, feature, threshold):\n",
    "        X_left, X_right, y_left, y_right = \n",
    "        H_y = \n",
    "        p = \n",
    "        \n",
    "        #TODO\n",
    "        \n",
    "        return ig\n",
    "\n",
    "    def best_split(self, X, y):\n",
    "\n",
    "        #TODO\n",
    "            \n",
    "        return best_feature, best_threshold\n",
    "\n",
    "    def build_tree(self, X, y, depth=0):\n",
    "        if self.is_splitting_finished(depth, len(X.columns), len(X)):\n",
    "            return None\n",
    "\n",
    "        best_feature, best_threshold = self.best_split(X, y)\n",
    "        X_left, X_right, y_left, y_right = self.split(X, y, best_feature, best_threshold)\n",
    "\n",
    "        left_node = self.build_tree(X_left, y_left, depth=depth + 1)\n",
    "        right_node = self.build_tree(X_right, y_right, depth=depth + 1)\n",
    "\n",
    "        value = None\n",
    "        if left_node is None or right_node is None:\n",
    "            true_value = len(y[y['diagnosis'] == 1])\n",
    "            false_value = len(y[y['diagnosis'] == 0])\n",
    "            if true_value >= false_value:\n",
    "                value = 1\n",
    "            else:\n",
    "                value = 0\n",
    "\n",
    "        return Node(feature=best_feature, threshold=best_threshold, left=left_node, right=right_node, value=value)\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        self.root = self.build_tree(X, y)\n",
    "\n",
    "    def predict(self, X):\n",
    "        tree = self.root\n",
    "        predicted_value = []\n",
    "        for index in list(X.index):\n",
    "            data = X.loc[index]\n",
    "            current_tree = tree\n",
    "            for depth in range(self.max_depth):\n",
    "                if Node.is_leaf(current_tree):\n",
    "                    predicted_value.append(current_tree.value)\n",
    "                    break\n",
    "                feature = current_tree.feature\n",
    "                threshold = current_tree.threshold\n",
    "                if data[feature] <= threshold:\n",
    "                    current_tree = current_tree.left\n",
    "                if data[feature] > threshold:\n",
    "                    current_tree = current_tree.right\n",
    "\n",
    "        return predicted_value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e2197f0",
   "metadata": {},
   "source": [
    "<font face=\"Times New Roman\" size=4><div dir=ltr>\n",
    "## Data Prepration (20 points)\n",
    "In this section, you must perform a good EDA for data. Then split it into train and validation data. We will then use the validation data to find the best model hyperparameters.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "da5a4d94",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-22T21:30:26.199958Z",
     "start_time": "2022-10-22T21:30:26.192910Z"
    }
   },
   "outputs": [],
   "source": [
    "breast_cancer_pdf = pd.read_csv(\"breast_cancer.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "27207399",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-22T21:30:28.478997Z",
     "start_time": "2022-10-22T21:30:28.476044Z"
    }
   },
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "39ba4c34",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-22T21:30:38.003703Z",
     "start_time": "2022-10-22T21:30:37.996292Z"
    }
   },
   "outputs": [],
   "source": [
    "\n",
    "X = \n",
    "\n",
    "y = \n",
    "\n",
    "x_train, x_val, y_train, y_val = train_test_split(X, y, test_size=0.70, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cefd7a92",
   "metadata": {},
   "source": [
    "<font face=\"Times New Roman\" size=4><div dir=ltr>\n",
    "## Training And Tuning Hyperparameters (20 points)\n",
    "In this section, you only need to find the best hyperparameters for your model. You can test different values and permutations of hyperparameters by adding them to the lists below. Your model must have at least accuracy=0.85 on validation data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "assigned-estate",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-22T21:36:15.733600Z",
     "start_time": "2022-10-22T21:36:15.730426Z"
    }
   },
   "outputs": [],
   "source": [
    "max_depths = []\n",
    "min_samples_splits = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58003410",
   "metadata": {},
   "outputs": [],
   "source": [
    "best_max_depth = None\n",
    "best_min_samples_split = None\n",
    "best_accuracy = 0\n",
    "best_model = None\n",
    "for max_depth in max_depths:\n",
    "    for min_samples_split in min_samples_splits:\n",
    "        clf = DecisionTree(max_depth, min_samples_split)\n",
    "        clf.fit(x_train, y_train)\n",
    "        y_val_pred = clf.predict(x_val)\n",
    "        y_train_pred = clf.predict(x_train)\n",
    "        accuracy = accuracy_score(y_val_pred, y_val)\n",
    "        train_accuracy = accuracy_score(y_train_pred, y_train)\n",
    "        print(f\"accuracy of training set for [min_samples_splits=???-max_depths=???] ={train_accuracy}\")\n",
    "        print(f\"accuracy of validation set for [min_samples_splits=???-max_depths=???] ={accuracy}\")\n",
    "        print(\"------------------------------------------------\")\n",
    "        if accuracy >= best_accuracy:\n",
    "            best_accuracy = accuracy\n",
    "            best_max_depth = max_depth\n",
    "            best_min_samples_split = min_samples_split\n",
    "            best_model = clf"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
